#include <iostream>
using namespace std;

typedef char DataType;

//二叉树数据结构 
struct node
{
	DataType info ; //存放结点数据 
	struct node *lchild , *rchild ; //指向左右孩子的指针 
};

typedef struct node *BiTree ;

/*创建二叉树
  函数名：createBiTree
  参数：无
  返回值：二叉树根结点指针
  */
BiTree createBiTree(void)
{
	//请在此处填写代码， 完成二叉树和创建，返回值是二叉树的根结点指针
    /********** Begin **********/
    // create root 
    BiTree node; 
    DataType info;
    cin >> info;
    if ('#' == info) {
        return NULL;
    } else {
        node = new struct node;
        if (NULL == node) {
            printf("Out of Space!\n");
            return NULL;
        };
        node->info = info;
        node->lchild = createBiTree();
        node->rchild = createBiTree();
        return node;
    }
    /********** End *********/
}

void visit(BiTree T) //输出结点T的数据
{
	cout<<T->info ;
}

void inOrder(BiTree root)
{
	if(root == NULL) return ;
	inOrder(root->lchild);
	visit(root);
	inOrder(root->rchild);
}

int main(void)
{
	BiTree root = createBiTree();
	inOrder(root);
}
